<TITLE>prob007: all-interval series</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob007: all-interval series</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.ubc.ca/spider/hoos/">
          <B>Holger Hoos</B></A> 
          <ADDRESS><a href="mailto:hoos@cs.ubc.ca">
          hoos@cs.ubc.ca</a></ADDRESS>
</TABLE>
</CENTER>


<HR><!------------------------------------------------------------------------>
<H3> Results </H3>

<P>
These problems appear to be hard for
local 
search methods. 

<P>
<A HREF="http://www.cs.ubc.ca/spider/hoos/publ-ai.html#phd">
Stochastic Local Search - Methods, Models, Applications 
(PhD thesis, TU Darmstadt, 1998)</A>
shows that the order 12 problem (which encodes into
just 265 variables and 5666 clauses) causes great difficulties
even for the very best local search methods for SAT. 

<P>
Complete methods using global constraints like  the all-different and
cycle constraints have little difficulty finding single solutions.
Finding all solutions appears to remain a challenge, and may
be a good test bed for symmetry methods.


<P>
<A HREF="helmut.pdf">
A Note on CSPLIB prob007
</A>
by Simonis and Beldiceanu shows that CHIP, using
global constraints, can find a single solution without
search. Finding all solutions is difficult even with the
efficient cycle constraint. 

<P>
In musical composition, 
we usually might want to find more than one solution (if it
exists); furthermore, the very regular interval structure of 
the single solutions found by Simonis and Beldiceanu
makes them potentially less interesting than other, more irregular solutions.
The context of the composition may also add additional 
constraints on the series. 

<P>
<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.

